package leetcode.binarytree;

import leetcode.TreeNode;
import leetcode.TreeNodeUtil;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Cheng Jun
 * Description: 找到某个节点的所有祖先节点
 * @version 1.0
 * @date 2021/12/12 23:32
 */
public class findAncestor {

    //    1
    //  2   3
    //4   5    6
    static boolean flag = false;

    public static void main(String[] args) {
        TreeNode treeNode = TreeNodeUtil.getBT(new Object[]{3, 5, 1, 6, 2, 0, 8, null, null, 7, 4});
        LinkedList<TreeNode> ancestorList = new LinkedList<>();
        TreeNode a = new TreeNode(4);
        findAncestor(treeNode, a, ancestorList);

    }

    private static void findAncestor(TreeNode root, TreeNode node, Deque<TreeNode> ancestorList) {

        if (root != null && !flag) {
            ancestorList.add(root);
            if (root.val != node.val) {
                findAncestor(root.left, node, ancestorList);
                findAncestor(root.right, node, ancestorList);
                if (!flag) {
                    ancestorList.remove(root);
                }
            } else {
                flag = true;
                return;
            }
        }

    }
}
